tree

Red and black tree implementation

The red-black tree structure is known for its balanced and efficient random access. In the actual use process, its efficiency is beyond imagination (the more nodes, the higher efficiency). In most cases, the number of nodes searched is less than one-half of the total number of nodes.The longest query path does not exceed one-half of the total query path plus the distance of one node.

The red-black tree with black and red to identify the root node and end with the leaf node has both advantages and disadvantages of (the advantages outweigh the disadvantages, of course) :

Advantages: Keep the height of the tree balanced when querying the nodes many times (no more than three rotations in rotation and no more than two rotations in insertion data);

Disadvantage: Redundant expenditure caused by tree rotation.

Insertion of red-black trees:

You can see from the picture ,Red and black tree root node (the node 20) ,The left side of the node (node 10) is smaller than the root node ,The node (30) node on the right side is greater than the root node , the right side node (parent node 30) is less than the right son node (node 40),No matter how many nodes the mangrove tree has, it balances in this way (The root node or branch node is larger than their left node and smaller than their right node). 

A red-black tree, in the form of small left big right to traverse the query,Query to the stop empty nodes ,And  returning to an  empty node previous node As the parent node to insert (If less than the parent node as insert the left  node of the parent node ,If is greater than the parent node as insert the right node of the parent node) ,Refer to the following code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 //Returns the location of the node to be inserted
Test_Rb_tree_node_base* Test_Rb_tree::Test_M_lower_bound(Test_Rb_tree_Ptr x,Test_Rb_tree_Ptr y,unsigned int val)
{
    while (x != 0)
    {
        int nless = compare_less(x, val);
        if (-1 == nless)//The current node is less than the query to the nodes
            y = x, x = Left(x);
        else if (1 == nless)//The current node is greater than the query to the nodes
            x = Right(x);
        else//If equal, the data is no longer inserts, returned directly
            return 0;
    }

    return y;
}

Explain briefly… :
This article from the CSDN ,Because of Not Much time… ,Most of the content and pictures no modification,In the future, new articles try to avoid this situation…..

Back to the topic… :

Insert situation one ,Right node insert :

Insertion situation two ,Left node insert :

Insertion situation three ,The root node left rotation :

Can be seen from the above example :

  1. The same color will not appear between the parent node and the node when the red-black tree is not moving(For example, they are all red) ;
  2. The root node is black when the red-black tree is not moving ;
  3. Node disconnection occurs during the rotation of the red-black tree ,Rotation to complete recovery for the new tree structure ;
  4. Red and black tree structure is suitable for random access ,It is more efficient to use linked list structure for sequential access;

This is the end of the article ,Very thank you for your reference.
My English level is average ,Most of the vocabulary is translated through web-based software ,Wrong place please forgive me…
GitHub download address : source file!
CSDN: Blog address!